package com.tgy.leetcode;

import java.util.Arrays;

/**
 * @Author: tgy
 * @Date: 2020/12/27 下午8:38
 *
 * https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
 */
public class _84_柱状图中最大的矩形_02 {

    public int largestRectangleArea(int[] heights) {

        if (heights == null || heights.length == 0) {

            return 0;
        }

        int[] leftToRight = new int[heights.length];
        int[] rightToLeft = new int[heights.length];

        /**
         * from left to right
         */

        leftToRight[0] = -1;
        for (int i = 1; i < heights.length ; i++) {

            int curVal = heights[i];
            leftToRight[i] = -1;
            int preIndex = i - 1;
            while (preIndex >= 0) {

                if (heights[preIndex] <= curVal) {

                    leftToRight[i] = (heights[preIndex] == curVal)?leftToRight[preIndex]:preIndex;
                    break;
                } else {
                    preIndex = leftToRight[preIndex];
                }
            }
        }


        rightToLeft[heights.length - 1] = heights.length;
        for (int i = heights.length - 2; i >= 0; i--) {

            int curVal = heights[i];
            rightToLeft[i] = heights.length;
            int nextIndex = i+1;
            while (nextIndex < heights.length) {

                if (heights[nextIndex] <= curVal) {

                    rightToLeft[i] = (heights[nextIndex] == curVal) ? rightToLeft[nextIndex]:nextIndex;
                    break;
                }else {
                    nextIndex = rightToLeft[nextIndex];
                }
            }
        }

        int max = 0;
        for (int i = 0; i < heights.length; i++) {
            max = Math.max(max,heights[i] * (rightToLeft[i] - leftToRight[i] - 1));
        }

        return max;
    }
}
